package com.ttx.algorithm.datastruct.tree;

/**
 * 二叉查找树
 *
 * <p>
 *     什么是二叉查找树?二叉查找树也叫二叉搜索树.
 *     对于二叉查找树的每个节点,
 *     它的左子树上的任意节点的值,都小于它本身的值,
 *     它的右子树上的任意节点的值都大于它本身的值.
 *
 *
 * <p>
 *     根据极客时间<数据结构与算法之美> 24节所写
 *
 * @author TimFruit
 * @date 19-2-2 上午10:56
 */
public class BinarySearchTree {

    private Node root;



    public Node find(int data){
        Node p=root;

        while(p != null){
            if(p.data == data){
                return p;
            }
            if(p.data < data){
                p=p.left;
            }else {
                p=p.right;
            }
        }

        return null;
    }


    public Node insert(int data){
        if(root == null){
            root=new Node(data);
            return root;
        }

        Node p=root;
        while(p != null){
            if(data < p.data){
                if(p.left != null){
                    p=p.left;
                }else{
                    p.left=new Node(data);
                    return p.left;
                }

            }else{
                if(p.right != null){
                    p=p.right;
                }else {
                    p.right=new Node(data);
                    return p.right;
                }
            }

        }

        return null;
    }


    public Node remove(int data){
        // 1. 查找对应节点
        Node target=root;
        Node targetParent=null;  //目标节点的父节点
        while(target != null && target.data != data){
            targetParent=target;
            if(data < target.data){
                target=target.left;
            }else {
                target=target.right;
            }
        }
        if(target == null){
            return null;
        }


        // 2. 删除对应节点, 分3种情况
        // 2.1) 目标节点有2个子节点  左子树 < 右子树
        if(target.left != null && target.right != null){
            //取右子树中的最小节点,
            //和目标节点替换
            Node minP=target.right;//右子树最小节点
            Node minPP=null; //右子树最小节点的父节点
            while(minP.left != null){
                minPP=minP;
                minP=minP.left;
            }
            if(minPP != null){
                minPP.left=minP.right;  //将右子树最小节点minP的右子节点移动到minPP的左子节点
            }else {
                target.right=minP.right;
            }

            //准备删除目标节点, 讲目标节点的两个子节点转移到minP对应的子节点中去
            minP.left=target.left;
            minP.right=target.right;
            if(targetParent!=null){
                if(targetParent.left == target){
                    targetParent.left=minP;
                }else{
                    targetParent.right=minP;
                }
            }else {
                root=minP;
            }

            return target;
        }


        // 2.2) 目标节点只有一个子节点, 直接使用子节点替换目标节点即可,
        // 2.3) 目标节点没有子节点,直接删除即可,即赋值为null
        Node child=null;
        if(target.left != null){
            child=target.left;
        }else if(target.right !=null ){
            child=target.right;
        }

        if(targetParent == null){//目标节点为根节点
            root=child;
            return target;
        }
        if(targetParent.left==target){
            targetParent.left=child;
        }else {
            targetParent.right=child;
        }
        return target;
    }








    private void clearChildNode(Node p){
        p.left=null;
        p.right=null;
    }


    public static class Node{
        private int data;
        private Node left;
        private Node right;


        public Node(int data) {
            this.data = data;
        }

    }


}
